package sort.onlogn.my_quick_sort_test;

import java.util.Arrays;

/**
 * @author yeyangtao created at 10:18 2020/12/12
 */
public class QuickSort1212 {
    public static void main(String[] args) {
        int[] a = new int[]{4, 3, 2, 8, 5, 0, 33, 77, 44, 68};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort(int[] a, int l, int r) {
        if (l >= r) return;
        int p = partition(a, l, r);
        quickSort(a, l, p - 1);
        quickSort(a, p + 1, r);
    }

    private static int partition(int[] a, int l, int r) {
        int pivot = a[r];
        int index = l;
        for (int i = l; i <= r; i++) {
            if (a[i] < pivot) {
                //减少交换次数
                if (i == index)
                    index++;
                else {
                    int temp = a[i];
                    a[i] = a[index];
                    a[index] = temp;
                    index++;
                }
            }
        }
        int temp = a[index];
        a[index] = pivot;
        a[r] = temp;
        return index;
    }
}
